//public class Test {
//    public static void main(String[] args) {
//        Object locker = new Object();
//        Thread t = new Thread(()->{
//            synchronized (locker) {
//                System.out.println("wait 等待之前");
//                try {
//                    locker.wait();
//                } catch (InterruptedException e) {
//                    throw new RuntimeException(e);
//                }
//                System.out.println("wait 等待结束");
//            }
//        });
//
//        t.start();
//    }
//}
//
//public class Test {
//    public static void main(String[] args) throws InterruptedException {
//        Object locker = new Object();
//        Thread t1 = new Thread(()->{
//            synchronized (locker) {
//                System.out.println("t1 wait 之前");
//                try {
//                    locker.wa
//                }catch (InterruptedException e) {
//                    e.printStackTrace();
//                }
//                System.out.println("t1 wait 之后");
//            }
//        });
//
//        Thread t2 = new Thread(()-> {
//            try {
//                Thread.sleep(3000);
//                //让 t1 线程有时间进入到wait状态
//                synchronized (locker) {
//                    System.out.println("t2 notify 之前");
//                    locker.notify();
//                    System.out.println("t2 notify 之后");
//                }
//            }catch (InterruptedException e) {
//                e.printStackTrace();
//            }
//        });
//
//        t1.start();
//        t2.start();
//    }
//}

class Singleton {
    private static Singleton instance = new Singleton();

    public Singleton getInstance() {
        return instance;
    }

    //构造方法设成私有的, 在外部代码中不能new出实例
    private Singleton() {
    }
}
//
//public class Test {
//    public static void main(String[] args) throws InterruptedException {
//        for(int i = 0; i<10; i++) {
//            Thread a = new Thread(()->{
//                System.out.print("A");
//            });
//
//            Thread b = new Thread(()->{
//                try {
//                    Thread.sleep(1000);
//                } catch (InterruptedException e) {
//                    throw new RuntimeException(e);
//                }
//                System.out.print("B");
//            });
//
//            Thread c = new Thread(()->{
//                try {
//                    Thread.sleep(2000);
//                } catch (InterruptedException e) {
//                    throw new RuntimeException(e);
//                }
//                System.out.print("C");
//            });
//            a.start();
//            b.start();
//            c.start();
//            c.join();
//            System.out.println();
//        }
//    }
//}
//
//public class Test {
//    private static Object locker1 = new Object();
//    private static Object locker2 = new Object();
//    private static Object locker3 = new Object();
//
//    public static void main(String[] args) throws InterruptedException {
//        Thread t1 = new Thread(() -> {
//            try {
//                for (int i = 0; i < 10; i++) {
//                    synchronized (locker1) {
//                        locker1.wait();
//                    }
//                    System.out.print("A");
//                    synchronized (locker2) {
//                        locker2.notify();
//                    }
//                }
//            } catch (InterruptedException e) {
//                e.printStackTrace();
//            }
//        });
//
//        Thread t2 = new Thread(() -> {
//            try {
//                for (int i = 0; i < 10; i++) {
//                    synchronized (locker2) {
//                        locker2.wait();
//                    }
//                    System.out.print("B");
//                    synchronized (locker3) {
//                        locker3.notify();
//                    }
//                }
//            } catch (InterruptedException e) {
//                e.printStackTrace();
//            }
//        });
//
//        Thread t3 = new Thread(() -> {
//            try {
//                for (int i = 0; i < 10; i++) {
//                    synchronized (locker3) {
//                        locker3.wait();
//                    }
//                    System.out.println("C");
//                    synchronized (locker1) {
//                        locker1.notify();
//                    }
//                }
//            } catch (InterruptedException e) {
//                e.printStackTrace();
//            }
//        });
//        t1.start();
//        t2.start();
//        t3.start();
//
//        Thread.sleep(1000);
//
//        // 从线程 t1 启动
//        synchronized (locker1) {
//            locker1.notify();
//        }
//    }
//}
//
//public class Test {
//    public static void main(String[] args) throws InterruptedException {
//        Object locker1 = new Object();
//        Object locker2 = new Object();
//        Object locker3 = new Object();
//
//        Thread a = new Thread(()->{
//           for(int i = 0 ; i<10 ;i++) {
//               synchronized (locker1) {
//                   try {
//                       locker1.wait();
//                   } catch (InterruptedException e) {
//                       throw new RuntimeException(e);
//                   }
//                   System.out.print("A");
//                   synchronized (locker2) {
//                       locker2.notify();
//                   }
//               }
//           }
//        });
//
//        Thread b = new Thread(()->{
//            for (int i = 0; i < 10; i++) {
//                synchronized (locker2) {
//                    try {
//                        locker2.wait();
//                    } catch (InterruptedException e) {
//                        throw new RuntimeException(e);
//                    }
//                    System.out.print("B");
//                    synchronized (locker3) {
//                        locker3.notify();
//                    }
//                }
//            }
//        });
//
//        Thread c = new Thread(()->{
//            for (int i = 0; i < 10; i++) {
//                synchronized (locker3){
//                    try {
//                        locker3.wait();
//                    }catch (InterruptedException e) {
//                        e.printStackTrace();
//                    }
//                }
//                System.out.println("C");
//                synchronized (locker1) {
//                    locker1.notify();
//                }
//            }
//        });
//
//        a.start();
//        b.start();
//        c.start();
//        Thread.sleep(1000);
//        synchronized (locker1) {
//            locker1.notify();
//        }
//    }
//}

class Solution {
    public int[][] matrixBlockSum(int[][] mat, int k) {
        int[][] sum = new int[mat.length+1][mat[0].length+1];
        for(int i = 1; i<sum.length; i++) {
            for(int j = 1; j<sum[0].length; j++) {
                sum[i][j]  = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mat[i-1][j-1];
            }
        }

        for(int i = 1; i<sum.length; i++) {
            for(int j = 1; j<sum[0].length; j++) {
                System.out.print(sum[i][j]+" ");
            }
            System.out.println();
        }

        int[][] ret = new int[mat.length][mat[0].length];

        for(int i = 1; i<sum.length; i++) {
            for(int j = 1; j<sum[0].length; j++) {
                int x1 = Math.max(1,i-k);
                int y1 = Math.max(1, j-k);
                int x2 = Math.min(sum.length-1,i+k);
                int y2 = Math.min(sum[0].length-1,j+k);

                ret[i-1][j-1] = sum[x2][y2] - sum[x2][y1-1] - sum[x1-1][y2] + sum[x1-1][y1-1];
            }
        }

        return ret;
    }
}

public class Test {
    public static void main(String[] args) {

    }
}


















